{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Move All Balls to Each Box"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移动所有球到每个盒子所需的最小操作数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个盒子。给你一个长度为 <code>n</code> 的二进制字符串 <code>boxes</code> ，其中 <code>boxes[i]</code> 的值为 <code>'0'</code> 表示第 <code>i</code> 个盒子是 <strong>空</strong> 的，而 <code>boxes[i]</code> 的值为 <code>'1'</code> 表示盒子里有 <strong>一个</strong> 小球。</p>\n",
    "\n",
    "<p>在一步操作中，你可以将 <strong>一个</strong> 小球从某个盒子移动到一个与之相邻的盒子中。第 <code>i</code> 个盒子和第 <code>j</code> 个盒子相邻需满足 <code>abs(i - j) == 1</code> 。注意，操作执行后，某些盒子中可能会存在不止一个小球。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>n</code> 的数组 <code>answer</code> ，其中 <code>answer[i]</code> 是将所有小球移动到第 <code>i</code> 个盒子所需的 <strong>最小</strong> 操作数。</p>\n",
    "\n",
    "<p>每个 <code>answer[i]</code> 都需要根据盒子的 <strong>初始状态</strong> 进行计算。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>boxes = \"110\"\n",
    "<strong>输出：</strong>[1,1,3]\n",
    "<strong>解释：</strong>每个盒子对应的最小操作数如下：\n",
    "1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。\n",
    "2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。\n",
    "3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>boxes = \"001011\"\n",
    "<strong>输出：</strong>[11,8,5,4,3,4]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == boxes.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2000</code></li>\n",
    "\t<li><code>boxes[i]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-move-all-balls-to-each-box](https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-move-all-balls-to-each-box](https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"110\"', '\"001011\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a=[]\n",
    "        t=0\n",
    "        s=len(nums)\n",
    "        x=s\n",
    "        p=0\n",
    "        flag=False\n",
    "        for i in nums:\n",
    "            if i==1:\n",
    "                flag=True\n",
    "                p+=1\n",
    "        if flag:\n",
    "            return x-p\n",
    "        \n",
    "\n",
    "        while True:\n",
    "            t+=1\n",
    "            for i in range(s-1):\n",
    "                nums[i]=gcd(nums[i],nums[i+1])\n",
    "                if nums[i]==1:\n",
    "                    return t+x-1\n",
    "            nums.pop()\n",
    "            s-=1\n",
    "                \n",
    "            if s==1:\n",
    "                return -1\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if reduce(gcd, nums) > 1:\n",
    "            return -1\n",
    "        if min(nums) == 1:\n",
    "            return sum([1 for i in nums if i > 1]) \n",
    "        n = len(nums)\n",
    "        d = n - 1\n",
    "        for i in range(n - 1):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if tmp == 1:\n",
    "                    d = min(d, j - i)\n",
    "                    break\n",
    "        return d + n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums)>1:\n",
    "            return -1\n",
    "        n=len(nums)\n",
    "        cnt1=sum(x==1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n-cnt1\n",
    "\n",
    "        min_size=n\n",
    "        for i in range(n):\n",
    "            g=0\n",
    "            for j in range(i,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1:\n",
    "                    min_size=min(min_size,j-i)\n",
    "                    break\n",
    "        return min_size+n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "                # 如果所有数的gcd>1，return -1\n",
    "        # 1如果有1，return n-count1\n",
    "        # 2如果没有1，return minsize-1+n-1\n",
    "        from math import gcd\n",
    "        if gcd(*nums)>1:return -1\n",
    "        cnt1=sum(num==1 for num in nums)\n",
    "        n=len(nums)\n",
    "        if cnt1:return n-cnt1\n",
    "        minsize=n\n",
    "        for i in range(n):\n",
    "            g=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize,j-i+1)\n",
    "                    break \n",
    "        return minsize+n-2\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1 != 0:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        min_len = float('inf')\n",
    "        n = len(nums)\n",
    "        one_cnt = nums.count(1)\n",
    "        if one_cnt:\n",
    "            return n - one_cnt\n",
    "        for i in range(n - 1):\n",
    "            g = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_len = min(min_len, j - i + 1)\n",
    "        return n - 1 + (min_len - 1) if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        minn=9999999\n",
    "        if 1 in nums:\n",
    "            return len(nums)-nums.count(1)\n",
    "        l=len(nums)\n",
    "        temp2=0\n",
    "        for i in range(l-1):\n",
    "            temp=nums[i]\n",
    "            for j in range(i+1,l):\n",
    "                if math.gcd(temp,nums[j])==1:\n",
    "                    temp=math.gcd(temp,nums[j])\n",
    "                    if j-i<minn:\n",
    "                        minn=j-i\n",
    "                    temp2=-1\n",
    "                else:\n",
    "                    temp=math.gcd(temp,nums[j])\n",
    "            if temp2==0:\n",
    "                return -1\n",
    "        return l+minn-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) >1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n-cnt1\n",
    "        minsize = n\n",
    "        for i in range(n):\n",
    "            g =  0\n",
    "            for j in range(i,n):\n",
    "                g = gcd(g,nums[j])\n",
    "                if g == 1:\n",
    "                    minsize = min(minsize,j-i)\n",
    "                    break\n",
    "        return minsize+n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        # 质因数分解 \r\n",
    "        # 如果 所有数字都有相同质因数那么返回 -1 \r\n",
    "        # 否则返回最快变1操作数 + (len(num1) - 1)\r\n",
    "\r\n",
    "        # 我以为随便选两个数，，，，绷不住了 \r\n",
    "        # \r\n",
    "        n = len(nums)\r\n",
    "        # def divx(x: int) -> List[int]:\r\n",
    "        #     dx = []\r\n",
    "        #     for i in range(2, isqrt(x) + 1):\r\n",
    "        #         if x % i == 0:\r\n",
    "        #             dx.append(i)\r\n",
    "        #             while x % i == 0:\r\n",
    "        #                 x //= i \r\n",
    "        #     if x > 1:\r\n",
    "        #         dx.append(x)\r\n",
    "        #     return dx\r\n",
    "                \r\n",
    "        # res = inf \r\n",
    "        # for x in nums:\r\n",
    "        #     d = divx(x)\r\n",
    "        #     dp = [[inf] * (1 << len(d)) for _ in range(n + 1)]\r\n",
    "        #     for i in range(n + 1):\r\n",
    "        #         dp[i][0] = 0\r\n",
    "        #     for i in range(n):\r\n",
    "        #         m = 0\r\n",
    "        #         for k, y in enumerate(d):\r\n",
    "        #             if nums[i] % y == 0:\r\n",
    "        #                 m |= (1 << k) \r\n",
    "        #         for j in range(1 << (len(d))):\r\n",
    "        #             dp[i + 1][j] = min(dp[i][j], dp[i][j&m] + 1)\r\n",
    "        #     if dp[-1][- 1] == inf:\r\n",
    "        #         return -1 \r\n",
    "        #     res = min(res, dp[-1][-1] + (n - 1)) \r\n",
    "        #     print(dp)\r\n",
    "        # return res if res != inf else -1 \r\n",
    "        cnt = sum(x == 1 for x in nums)\r\n",
    "        if cnt:\r\n",
    "            return n - cnt \r\n",
    "        \r\n",
    "        res = inf\r\n",
    "        for i in range(n):\r\n",
    "            g = nums[i]\r\n",
    "            for j in range(i, n):\r\n",
    "                g = gcd(g, nums[j])\r\n",
    "                if g == 1:\r\n",
    "                    res = min((j - i) + (n - 1), res)\r\n",
    "        return res if res != inf else -1 \r\n",
    "    \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tmp = nums.copy()\n",
    "        ans = n-nums.count(1)\n",
    "        while tmp:\n",
    "            for i in range(len(tmp)-1):\n",
    "                tmp[i] = gcd(tmp[i], tmp[i+1])\n",
    "                if tmp[i] == 1:\n",
    "                    return ans\n",
    "            ans += 1 # length of [i,j] interval (that make 1 happen) + 1\n",
    "            tmp.pop()\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        cnt1 = sum(num == 1 for num in nums)\n",
    "        \n",
    "        if cnt1 > 0:\n",
    "            return n - cnt1\n",
    "        \n",
    "        min_cnt = inf\n",
    "\n",
    "        for i in range(n-1):\n",
    "            gcd_res = nums[i]\n",
    "            for j in range(i+1, n):\n",
    "                gcd_res = gcd(nums[j], gcd_res)\n",
    "                \n",
    "                if gcd_res == 1:\n",
    "                    min_cnt = min(min_cnt, j - i)\n",
    "                    break\n",
    "                    \n",
    "        return n + min_cnt - 1 if min_cnt < inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, A: List[int]) -> int:\n",
    "        return len(A) - A.count(1) if 1 in A else -1 if gcd(*A) != 1 else len(A) + min(j - i for i, j in combinations(range(len(A) + 1), 2) if 1 == gcd(*A[i: j])) - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def gcd(x,y):\n",
    "            if y%x==0 or x%y==0:\n",
    "                return min(x,y)\n",
    "            return gcd(max(x,y)%min(x,y),min(x,y))\n",
    "        res=nums[0]\n",
    "        for num in nums:\n",
    "            res=gcd(res,num)\n",
    "        if res>1:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                cnt+=1\n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(n):\n",
    "                res=nums[i]\n",
    "                for j in range(1,x):\n",
    "                    if i+j<n:\n",
    "                        res=gcd(res,nums[i+j])\n",
    "                        if res==1:\n",
    "                            return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "        \n",
    "        left,right=n-1,2*n-1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid-n+1):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        min_len = float('inf')\n",
    "        n = len(nums)\n",
    "        one_cnt = nums.count(1)\n",
    "        if one_cnt:\n",
    "            return n - one_cnt\n",
    "        for i in range(n - 1):\n",
    "            g = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_len = min(min_len, j - i + 1)\n",
    "        return n - 1 + (min_len - 1) if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        n_one = nums.count(1)\n",
    "        if n_one:\n",
    "            return n - n_one\n",
    "        \n",
    "        min_len = n\n",
    "        for i in range(n):\n",
    "            min_gcd = 0\n",
    "            for k in range(i,n):\n",
    "                min_gcd = gcd(min_gcd, nums[k])\n",
    "                if min_gcd == 1:\n",
    "                    min_len = min(min_len, k - i)\n",
    "                    break\n",
    "            \n",
    "            if min_len == 1:\n",
    "                break\n",
    "\n",
    "        return min_len + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a:int,b:int)->int:\n",
    "            while b != 0:\n",
    "                a,b = b,a%b\n",
    "            return a\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        dis = inf\n",
    "        for i in range(n):\n",
    "            ones += 1 if nums[i] == 1 else 0\n",
    "            a = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                a = gcd(a,nums[j])\n",
    "                if a == 1:\n",
    "                    dis = min(dis,j-i)\n",
    "        if ones:\n",
    "            return n - ones\n",
    "        elif dis == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return n + dis - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a1 = 0\n",
    "        tmp = nums[0]\n",
    "        if nums[0]==1:\n",
    "            a1+=1\n",
    "        for i in nums[1:]:\n",
    "            tmp=gcd(tmp,i)\n",
    "            if i==1:\n",
    "                a1+=1\n",
    "        if tmp!=1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        if a1>0:\n",
    "            return n-a1\n",
    "        res = n\n",
    "        for i in range(n):\n",
    "            t = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                t = gcd(t,nums[j])\n",
    "                if t==1:\n",
    "                    res=min(res,j-i+1)\n",
    "        return n+res-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        t = sum(1 for i in nums if i == 1)\n",
    "        if t:\n",
    "            return n - t\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        a = nums.copy()\n",
    "        for t in range(1, n):\n",
    "            a.pop()\n",
    "            for i, c in enumerate(a):\n",
    "                a[i] = gcd(c, nums[i + t])\n",
    "                if a[i] == 1:\n",
    "                    return n + t - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt_1 = 0\n",
    "        for num in nums:\n",
    "            cnt_1 += (num == 1)\n",
    "        if cnt_1 > 0:\n",
    "            return n - cnt_1\n",
    "        l = 1\n",
    "        f = copy.deepcopy(nums)\n",
    "        while l < n:\n",
    "            for i in range(0, n - l):\n",
    "                f[i] = gcd(f[i], nums[i + l])\n",
    "                if f[i] == 1:\n",
    "                    return n + l - 1\n",
    "            l += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def gcd(x, y):\n",
    "            while y:\n",
    "                tmp = y\n",
    "                y = x % y \n",
    "                x = tmp \n",
    "            return x \n",
    "        cnt = nums.count(1)\n",
    "        def check(start, end):\n",
    "            g = nums[start]\n",
    "            for i in range(start + 1, end + 1):\n",
    "                g = gcd(g, nums[i])\n",
    "            return g == 1 \n",
    "        if cnt > 0:\n",
    "            return n - cnt \n",
    "        l = 0\n",
    "        res = float('inf')\n",
    "        for r in range(n):\n",
    "            while l < r and check(l, r):\n",
    "                res = min(res, r - l + n - 1)\n",
    "                l += 1 \n",
    "        return res if res != float('inf') else - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 如果所有的相邻的两个数都大于 1，且 gcd 都大于 自身，意味着 gcd 不会更小，那么返回 -1\n",
    "        # 否则找到一个连续子数组，对其 gcd 得到第一个 1\n",
    "        # 以题目的 [2,6,3,4] 为例，我们得到了 [2, 6, 3, 1]\n",
    "        # 接下来用 1 和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        # 特殊地，如果数组中已经有 1 了，那么直接和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cnt += num == 1\n",
    "        if cnt > 0: return len(nums) - cnt\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            cnt = 0\n",
    "            for j in range(i+1, len(nums)):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                cnt += 1\n",
    "                if g == 1:# 从 i 到 j 的子数组 gcd 是 1， 那么我们就先对其 gcd，操作数为 cnt，再加上扩展的操作数为 len(nums) - 1\n",
    "                    ans = min(ans, len(nums) - 1 + cnt)\n",
    "                    break # 提前退出\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        a = []  # [GCD，相同 GCD 闭区间的右端点]\n",
    "        for i, x in enumerate(nums):\n",
    "            a.append([x, i])\n",
    "\n",
    "            # 原地去重，因为相同的 GCD 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "\n",
    "            if a[0][0] == 1:\n",
    "                # 这里本来是 i-a[0][1]+1，把 +1 提出来合并到 return 中\n",
    "                min_size = min(min_size, i - a[0][1])\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 原本如果数组里有1，那么最少操作数是 n - cnt\n",
    "        # 如果没有1，那么就最短的gcd为1的子数组构造出一个1\n",
    "        n = len(nums)\n",
    "        g = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            g = math.gcd(g,num)\n",
    "            if num == 1:\n",
    "                cnt+=1\n",
    "        if g!=1:\n",
    "            return -1\n",
    "        \n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        minsize = n+1\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize, j-i+1)\n",
    "        return minsize + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 如果相邻的两个数大于 1，且 gcd 都大于 自身，意味着 gcd 不会更小，那么返回 -1\n",
    "        # 否则找到一对，进行 gcd 直到等于 1，我们得到了一个 1\n",
    "        # 以题目的 [2,6,3,4] 为例，我们得到了 [2, 6, 3, 1]\n",
    "        # 接下来用 1 和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        # 特殊地，如果数组中已经有 1 了，那么直接和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cnt += num == 1\n",
    "        if cnt > 0: return len(nums) - cnt\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            cnt = 0\n",
    "            for j in range(i+1, len(nums)):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                cnt += 1\n",
    "                if g == 1:\n",
    "                    ans = min(ans, len(nums) - 1 + cnt)\n",
    "                    break\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=inf\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                ans=1\n",
    "                break\n",
    "            else:\n",
    "                g=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1: ans=min(ans,j-i+1)\n",
    "        print(ans)\n",
    "        if ans==inf:return -1\n",
    "        elif ans==1: return n-nums.count(1)\n",
    "        elif ans==2: return n\n",
    "        else: return ans-2+n\n",
    "        #n=4, ans=2\n",
    "        #n=3, ans=3\n",
    "        #n=5, ans=3\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        arr=nums\n",
    "        st=[]\n",
    "        min_size=n\n",
    "        for i,a in enumerate(arr):\n",
    "            for j in range(len(st)):\n",
    "                st[j][0]=gcd(st[j][0],a)\n",
    "            nst=[]\n",
    "            for v,j in st:\n",
    "                if len(nst)==0 or v!=nst[-1][0]:\n",
    "                    nst.append([v,j])\n",
    "            nst.append([a,i])\n",
    "            for j in range(len(nst)-1):\n",
    "                v,s,e=nst[j][0],nst[j][1],nst[j+1][1]-1\n",
    "            st=nst\n",
    "            if st[0][0]==1:\n",
    "                min_size=min(min_size,i-(st[1][1]-1)+1)\n",
    "            #print(st)\n",
    "            if len(st)>1 and st[-1][0]==st[-2][0]:\n",
    "                st.pop()\n",
    "        return min_size + n - 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1%num2)\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 1):\n",
    "                ones += 1\n",
    "        if(ones > 0):\n",
    "            return n - ones\n",
    "        min_size = float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if(tmp == 1):\n",
    "                    min_size = min(min_size, j-i+1)\n",
    "        if(min_size == float('inf')):\n",
    "            return -1\n",
    "        else:\n",
    "            return n - 1 + min_size - 1\n",
    "                \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a:int,b:int)->int:\n",
    "            while b != 0:\n",
    "                a,b = b,a%b\n",
    "            return a\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        a = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dis = inf\n",
    "        for i in range(n):\n",
    "            ones += 1 if nums[i] == 1 else 0\n",
    "            a[i][i] = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                a[i][j] = gcd(a[i][j-1],nums[j])\n",
    "                if a[i][j] == 1:\n",
    "                    dis = min(dis,j-i)\n",
    "        if ones:\n",
    "            return n - ones\n",
    "        elif dis == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return n + dis - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if 1 in nums:\n",
    "            return len(nums) - nums.count(1)\n",
    "        n = len(nums)\n",
    "        if reduce(gcd, nums) != 1:\n",
    "            return -1\n",
    "        for l in range(2, 51):\n",
    "            for i in range(n - l + 1):\n",
    "                if reduce(gcd, nums[i: i + l]) == 1:\n",
    "                    return l + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                count += 1\n",
    "        if count > 0:\n",
    "            return len(nums) - count\n",
    "        minlength = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if gcd(*nums[i:j]) == 1:\n",
    "                    minlength = min(minlength, j - i)\n",
    "        return minlength + len(nums) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            g = math.gcd(g,num)\n",
    "            if num == 1:\n",
    "                cnt+=1\n",
    "        if g!=1:\n",
    "            return -1\n",
    "        \n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        minsize = n+1\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize, j-i+1)\n",
    "        return minsize + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1%num2)\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 1):\n",
    "                ones += 1\n",
    "        if(ones > 0):\n",
    "            return n - ones\n",
    "        min_size = float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if(tmp == 1):\n",
    "                    min_size = min(min_size, j-i+1)\n",
    "        if(min_size == float('inf')):\n",
    "            return -1\n",
    "        else:\n",
    "            return n - 1 + min_size - 1\n",
    "                \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                count += 1\n",
    "        if count > 0:\n",
    "            return len(nums) - count\n",
    "        minlength = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if gcd(*nums[i:j]) == 1:\n",
    "                    minlength = min(minlength, j - i)\n",
    "        return minlength + len(nums) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for nu in nums:\n",
    "            if nu == 1:\n",
    "                cnt += 1\n",
    "        if cnt != 0:\n",
    "            return n - cnt\n",
    "        ans = 100\n",
    "        for i in range(n):\n",
    "            res = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                res = gcd(res, nums[j])\n",
    "                if res == 1:\n",
    "                    ans = min(ans, j - i + n - 1)\n",
    "                    break\n",
    "        if ans == 100:\n",
    "            return -1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1 :\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        \n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i + 1)\n",
    "                    break\n",
    "        \n",
    "        return min_size + n - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n, cnt1 = len(nums), sum(x==1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        \n",
    "        g, min_size = [], n\n",
    "        for i, x in enumerate(nums):\n",
    "            g.append([x, i])\n",
    "\n",
    "            j = 0\n",
    "            for p in g:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if g[j][0] == p[0]:\n",
    "                    g[j][1] = p[1]\n",
    "                else:\n",
    "                    j += 1\n",
    "                    g[j] = p\n",
    "            del g[j+1:]\n",
    "\n",
    "            if g[0][0] == 1:\n",
    "                min_size = min(min_size, i-g[0][1]+1)\n",
    "        return min_size + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def gcd(x,y):\n",
    "            if y%x==0 or x%y==0:\n",
    "                return min(x,y)\n",
    "            return gcd(max(x,y)%min(x,y),min(x,y))\n",
    "        res=nums[0]\n",
    "        for num in nums:\n",
    "            res=gcd(res,num)\n",
    "        if res>1:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                cnt+=1\n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(n):\n",
    "                res=nums[i]\n",
    "                for j in range(1,x):\n",
    "                    if i+j<n:\n",
    "                        res=gcd(res,nums[i+j])\n",
    "                        if res==1:\n",
    "                            return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "        \n",
    "        left,right=n-1,2*n-1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid-n+1):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt1 =sum(x == 1 for x in nums)        \n",
    "\n",
    "        if cnt1:\n",
    "            return n -cnt1\n",
    "        min_size = n\n",
    "        g = []\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            g.append([x,i])\n",
    "            ## 相同的 gcd 在一起\n",
    "            j = 0\n",
    "            for p in g :\n",
    "                p[0] = gcd(p[0],x)\n",
    "                if g[j][0]!=p[0]:\n",
    "                    j +=1\n",
    "                    g[j] = p\n",
    "                else:\n",
    "                    g[j][1] = p[1]\n",
    "            del g[j+1:]\n",
    "            if g[0][0] ==1:\n",
    "                min_size =min(min_size,i-g[0][1])\n",
    "        \n",
    "        return min_size +n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        if reduce(gcd, nums) != 1:\r\n",
    "            return -1\r\n",
    "        h = Counter(nums)\r\n",
    "        if h[1]:\r\n",
    "            return len(nums) - h[1]\r\n",
    "        for i in range(2, len(nums) + 1):\r\n",
    "            for j in range(0, len(nums) - i + 1):\r\n",
    "                if reduce(gcd, nums[j:j + i]) == 1:\r\n",
    "                    return len(nums) + i - 2\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ml=n=len(nums)\n",
    "        one=0\n",
    "        yes=False\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                one+=1\n",
    "            g=nums[i]\n",
    "            j=i\n",
    "            while g!=1 and j<n:\n",
    "                g=gcd(g,nums[j])\n",
    "                j+=1\n",
    "            if g==1:\n",
    "                ml=min(ml,j-i)\n",
    "                yes=True\n",
    "        if not yes :return -1\n",
    "        print(one,ml,n)\n",
    "        if ml==0:\n",
    "            return n-one\n",
    "        else:\n",
    "            return n+ml-2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        uniqNums = sorted(set(nums))\n",
    "        \n",
    "        N = len(nums)\n",
    "        ans = N\n",
    "        j = 0\n",
    "        for i in range(len(uniqNums)):\n",
    "            if i >= ans:\n",
    "                break\n",
    "            lower = uniqNums[i]\n",
    "            upper = lower + N - 1\n",
    "            while (j < len(uniqNums)) and uniqNums[j] <= upper:\n",
    "                j += 1\n",
    "            count = j - i\n",
    "            ans = min(ans, N - count)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "                \n",
    "        length = len(nums)\n",
    "        ret = length-1\n",
    "        nums.sort()\n",
    "        l_index = 0\n",
    "        r_index = 0\n",
    "\n",
    "        repeat_index = list() # the index repeat with the later element\n",
    "        repeat_presum = [0]*length # how many times repeat appear in the first i number\n",
    "        for i in range(length-1):\n",
    "            if nums[i]==nums[i+1]:\n",
    "                repeat_index.append(i)\n",
    "                repeat_presum[i+1]=repeat_presum[i]+1\n",
    "            else:\n",
    "                repeat_presum[i+1]=repeat_presum[i]\n",
    "\n",
    "\n",
    "        while l_index<length-1:\n",
    "            # move r_index to right position\n",
    "            l_num = nums[l_index]\n",
    "            max_num = l_num + length - 1\n",
    "            for i in range(r_index,length):\n",
    "                if nums[i]<=max_num:\n",
    "                    r_index=i\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            operations = l_index + (repeat_presum[r_index]-repeat_presum[l_index]) + (length-r_index-1)\n",
    "            ret = min(ret, operations)\n",
    "\n",
    "            # find same number\n",
    "            while l_index+1 < length and nums[l_index]==nums[l_index+1]:\n",
    "                l_index+=1\n",
    "            l_index+=1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        l, i = 0, 0\n",
    "        res = inf\n",
    "        dup = 0\n",
    "        while i < n:\n",
    "            right = nums[l] + n - 1\n",
    "            while i < n and nums[i] <= right:\n",
    "                if i >= 1 and nums[i] == nums[i-1]:\n",
    "                    dup += 1\n",
    "                i += 1\n",
    "            res = min(res, n - (i - l) + dup)\n",
    "            l += 1\n",
    "            if l < n and nums[l] == nums[l-1]:\n",
    "                dup -= 1\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        pres = [0, 1]\n",
    "        for i, num in enumerate(nums[1:], start=1):\n",
    "            if num == nums[i - 1]:\n",
    "                pres.append(pres[-1])\n",
    "            else:\n",
    "                pres.append(pres[-1] + 1)\n",
    "                \n",
    "        ans = n - 1\n",
    "        for i, num in enumerate(nums):\n",
    "            j = bisect.bisect_right(nums, num + n - 1)\n",
    "            ans = min(ans, n - (pres[j] - pres[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = (1 << 31)-1\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        repeat = 0\n",
    "        while right < n:\n",
    "            if right > 0 and nums[right-1] == nums[right]:\n",
    "                repeat += 1\n",
    "            while nums[left]+n-1 < nums[right]:\n",
    "                left += 1\n",
    "                if nums[left] == nums[left-1]:\n",
    "                    repeat -= 1\n",
    "            res = min(res, n-(right-left+1-repeat))\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        tmp = [nums[0]]\n",
    "        for i in range(1, n) :\n",
    "            if nums[i-1] != nums[i] :\n",
    "                tmp.append(nums[i])\n",
    "        n_t = len(tmp)\n",
    "        ans = inf\n",
    "        for i in range(n_t) :\n",
    "            ind = bisect_right(tmp,  tmp[i]+n-1)\n",
    "            ans = min(ans, n - ind + i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n,ans,x,same=len(nums),len(nums),0,0\n",
    "        for i in range(0,n):\n",
    "            if(i+1<n and nums[i]==nums[i+1]):same-=1;continue\n",
    "            while(x<n and nums[x]-nums[i]<n):\n",
    "                x+=1\n",
    "                if(x<n and nums[x]==nums[x-1]):same+=1\n",
    "            ans=min(ans,n-(x-i-same))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      nums.sort()\n",
    "      left = right = maxl = 0\n",
    "      repeat = [0] * n\n",
    "      k = 0\n",
    "      for i in range(1, n):\n",
    "        if nums[i] == nums[i-1]:\n",
    "          k += 1\n",
    "        repeat[i] = k\n",
    "      def findrepeat(i, j):\n",
    "        if i == 0:\n",
    "          return repeat[j]\n",
    "        if nums[i] == nums[i-1]:\n",
    "          return repeat[j] - repeat[i - 1] - 1\n",
    "        else:\n",
    "          return repeat[j] - repeat[i - 1]\n",
    "      while right < n:\n",
    "        if nums[right] - nums[left] < n:\n",
    "          maxl = max(maxl, right - left + 1 - findrepeat(left, right))\n",
    "          right += 1\n",
    "        else:\n",
    "          left += 1\n",
    "      return (n - maxl)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        ans = 1\n",
    "        overload = 0\n",
    "        for i in range(n):\n",
    "            if i != 0 and nums[i-1] == nums[i]:\n",
    "                overload += 1\n",
    "            while nums[i] - nums[j] > n - 1:\n",
    "                j += 1\n",
    "                if nums[j] == nums[j-1]:\n",
    "                    overload -= 1 \n",
    "            ans = max(ans, i - j + 1 - overload)\n",
    "        return n - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = (1 << 31)-1\n",
    "        n = len(nums)\n",
    "        dq = deque()\n",
    "        for num in nums:\n",
    "            while len(dq) and dq[0]+n-1 < num:\n",
    "                dq.popleft()\n",
    "            if not len(dq) or dq[-1]!=num:\n",
    "                dq.append(num)\n",
    "            res = min(res, n-len(dq))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        j = 0\n",
    "        total = 0\n",
    "        for i in range(len(nums)):\n",
    "            while j < len(nums) and nums[j] - nums[i] <= len(nums) - 1:\n",
    "                if j == 0 or nums[j] > nums[j - 1]:\n",
    "                    total += 1\n",
    "                j += 1\n",
    "            ans = min(ans, len(nums) - total)\n",
    "            if i == 0 or nums[i] > nums[i - 1]:\n",
    "                total -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        l = 0 # 左端点\n",
    "        r = 0 # 右端点\n",
    "        t = 0 # 表示滑动窗口内不需要改动的数的个数\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= n - 1:\n",
    "                # 不能有重复\n",
    "                if r > l and nums[r] != nums[r-1]:\n",
    "                    t += 1\n",
    "                elif r == l:\n",
    "                    t += 1\n",
    "                r += 1\n",
    "            l += 1\n",
    "            # n - t 表示需要改动的数的个数\n",
    "            ans = min(n-t, ans)\n",
    "            # 当nums[l] == nums[l-1] 时, 以nums[l-1]为左端点中 nums[l] 被当作重复值了\n",
    "            if l < n and nums[l] != nums[l-1]:\n",
    "                t -= 1\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nn = [a for a, b in pairwise(nums) if a != b] + [nums[-1]]\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        for i, num in enumerate(nn):\n",
    "            idx = bisect.bisect(nn, num + n - 1)\n",
    "            ans = min(ans, n - (idx - i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        l = 0\n",
    "        r = 0\n",
    "        t = 0\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= n - 1:\n",
    "                if r > l and nums[r] != nums[r-1]:\n",
    "                    t += 1\n",
    "                if r == l:\n",
    "                    t += 1\n",
    "                r += 1\n",
    "            l += 1\n",
    "            ans = min(n-t, ans)\n",
    "            if l < n and nums[l] != nums[l-1]:\n",
    "                t -= 1\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minOperations([44,28,33,49,4,2,35,28,25,38,47,20,14,30,27,38,42,14,34])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        l = 0 # 左端点\n",
    "        r = 0 # 右端点\n",
    "        t = 0 # 表示不需要改动的数的个数\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= n - 1:\n",
    "                # 不能有重复\n",
    "                if r > l and nums[r] != nums[r-1]:\n",
    "                    t += 1\n",
    "                elif r == l:\n",
    "                    t += 1\n",
    "                r += 1\n",
    "            l += 1\n",
    "            ans = min(n-t, ans)\n",
    "            # nums[l] == nums[l-1] 时 nums[l] 未被计算为“可用”\n",
    "            if l < n and nums[l] != nums[l-1]:\n",
    "                t -= 1\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minOperations([44,28,33,49,4,2,35,28,25,38,47,20,14,30,27,38,42,14,34])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        left,right = 0,0\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "        max_val = 0\n",
    "        for right in range(n):\n",
    "            if nums[right]<=nums[left]+n-1:\n",
    "              \n",
    "                visited.add(nums[right])\n",
    "                \n",
    "            else:\n",
    "                while nums[right]-nums[left]>=n:\n",
    "                    if nums[left] in visited:\n",
    "                        visited.remove(nums[left])\n",
    "                    left += 1\n",
    "                \n",
    "               \n",
    "        \n",
    "                visited.add(nums[right])\n",
    "           \n",
    "\n",
    "            max_val = max(len(visited),max_val)\n",
    "        return n-max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = n - 1\n",
    "        nums.sort()\n",
    "        snums = set(nums)\n",
    "        nums_no_dup = list(snums)\n",
    "        nums_no_dup.sort()\n",
    "        # print(nums, nums_no_dup)\n",
    "        for i, num in enumerate(nums_no_dup):\n",
    "            expect = i + n - 1\n",
    "            idx = self.findidx(nums_no_dup, len(nums_no_dup), num + n - 1)\n",
    "            res = min(res, (n - (idx - i)))\n",
    "            # print(i, num, n, idx, (n - (idx - i)), res)\n",
    "\n",
    "            newidx = bisect_right(nums_no_dup, num+n-1)\n",
    "            # print(idx, newidx)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def findidx(self, nums, n, target):\n",
    "        # print( nums, n, target)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                if mid < n-1 and nums[mid+1] > target:\n",
    "                    return mid + 1\n",
    "                left = mid + 1\n",
    "\n",
    "        return n\n",
    "                \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))  \n",
    "        ans = n\n",
    "        for i, start in enumerate(nums):\n",
    "            end = start + n - 1  \n",
    "            idx = bisect_right(nums, end)  # Find right insert position\n",
    "            uniqueLen = idx - i\n",
    "            ans = min(ans, n - uniqueLen)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # neetcode\n",
    "        length = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        res = length\n",
    "        r = 0\n",
    "        for l in range(len(nums)):\n",
    "            # range: nums[l], nums[l] + length - 1\n",
    "            while r < len(nums) and nums[r] < nums[l] + length:\n",
    "                r += 1\n",
    "            window = r - l \n",
    "            res = min(res, length - window)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        m = len(nums)  # 排重之后的数量\n",
    "        nums.sort()\n",
    "        ans = n\n",
    "        r = 0\n",
    "        for l in range(m):\n",
    "            mx = nums[l] + n - 1\n",
    "            r = max(r, l)\n",
    "            while r < m and nums[r] <= mx:\n",
    "                r += 1\n",
    "            ans = min(ans, l + n - r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            if nums[j] >= nums[i] + N:\n",
    "                cur = j - i\n",
    "                if cur > ret:\n",
    "                    ret = cur\n",
    "                while nums[j] >= nums[i] + N:\n",
    "                    i += 1\n",
    "        cur = n - i\n",
    "        if cur > ret:\n",
    "            ret = cur\n",
    "        return N - ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        m, left = len(nums), 0\n",
    "        for right in range(m):\n",
    "            if nums[right] - nums[left] >= n:\n",
    "                left += 1\n",
    "\n",
    "        return n - (m - left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        an = len(a)\n",
    "\n",
    "        cur = 0\n",
    "        r = 0\n",
    "        for l in range(an):\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\n",
    "                r += 1\n",
    "            cur = max(cur, r - l + 1)\n",
    "\n",
    "        return n - cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        new_nums = sorted(set(nums))\n",
    "        \n",
    "        for i in range(len(new_nums)):\n",
    "            left = new_nums[i]\n",
    "            right = left + n - 1\n",
    "            j = bisect_right(new_nums, right)\n",
    "            count = j - i\n",
    "            ans = min(ans, n - count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        ans = n\n",
    "        l = 0\n",
    "        for r, v in enumerate(nums):\n",
    "            while nums[l] < v - n + 1:\n",
    "                l += 1\n",
    "            \n",
    "            ans = min(ans, n - (r - l + 1))\n",
    "            \n",
    "        r = 0\n",
    "        for l, v in enumerate(nums):\n",
    "            while r + 1 < len(nums) and nums[r+1] <= v + n - 1:\n",
    "                r += 1\n",
    "            \n",
    "            ans = min(ans, n - (r - l + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        unique_nums = sorted(list(set(nums)))\n",
    "        ans = n - 1\n",
    "        m = len(unique_nums)\n",
    "        for i in range(m):\n",
    "            start_val, end_val = unique_nums[i], unique_nums[i] + n - 1\n",
    "            idx = bisect_right(unique_nums, end_val)\n",
    "            overlap = idx - i\n",
    "            if n - overlap < ans:\n",
    "                ans = n - overlap\n",
    "        return ans\n",
    "        # m = len(unique_nums)\n",
    "        # max_length = 1\n",
    "        # idx = 0\n",
    "        # while idx < m:\n",
    "        #     i = idx\n",
    "        #     while i + 1 < m and unique_nums[i+1] - unique_nums[i] == 1:\n",
    "        #         i += 1\n",
    "        #     if i - idx + 1 > max_length:\n",
    "        #         max_length = i - idx + 1\n",
    "        #     idx = i + 1\n",
    "        \n",
    "        # return n - max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        numsSize = len(nums)\n",
    "\n",
    "        numsUiqueSort = sorted(set(nums))\n",
    "        numsUiqueSortSize = len(numsUiqueSort)\n",
    "\n",
    "        retVal = numsSize\n",
    "        j = 0\n",
    "        for i in range(numsUiqueSortSize):\n",
    "            while (j < numsUiqueSortSize) and (numsUiqueSort[j] < numsUiqueSort[i] + numsSize):\n",
    "                j += 1\n",
    "            count = j - i\n",
    "            retVal = min(retVal, numsSize - count)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = set(nums)\n",
    "        nums = list(s)\n",
    "\n",
    "        nums.sort()\n",
    "        l, i = 0, 0\n",
    "        res = inf\n",
    "        while l < len(nums):\n",
    "            right = nums[l] + n - 1\n",
    "            while i < len(nums) and nums[i] <= right:\n",
    "                res = min(res, n - (i - l + 1))\n",
    "                i += 1\n",
    "            l += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(set(nums))\n",
    "        m, left = len(a), 0\n",
    "        for i in range(m):\n",
    "            if a[i] - a[left] >= n: left += 1\n",
    "        return n - (m - left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 第一点 重复元素必改 改成什么样子后面决定\n",
    "        target = len(nums)-1\n",
    "        t = len(nums)-len(set(nums))\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        # 滑动窗口 找到最大的窗口\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] > target:\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return t+len(nums)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(set(nums))\n",
    "        m, left = len(a), 0\n",
    "        for i in range(m):\n",
    "            if a[i] - a[left] >= n: left += 1\n",
    "        return n - (m - left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "\r\n",
    "        a = list(set(nums))\r\n",
    "        a.sort()\r\n",
    "        an = len(a)\r\n",
    "\r\n",
    "        cur = 0\r\n",
    "        r = 0\r\n",
    "        for l in range(an):\r\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\r\n",
    "                r += 1\r\n",
    "            cur = max(cur, r - l + 1)\r\n",
    "\r\n",
    "        return n - cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        nums = sorted(set(nums))\n",
    "       \n",
    "        # res = 1\n",
    "        # cur = 1\n",
    "        # l = 0\n",
    "        # n = len(nums)\n",
    "        # start = nums[l]\n",
    "        # for r in range(1, len(nums)):\n",
    "        #     if nums[r] <= start + n - 1:\n",
    "        #         cur += 1\n",
    "        #         res = max(res,cur)\n",
    "        #     else:\n",
    "        #         while l < r and nums[l] < nums[r] - n :\n",
    "        #             l += 1\n",
    "        #         cur = 1\n",
    "        #         start = nums[l]\n",
    "  \n",
    "        # return n - res\n",
    "\n",
    "        \n",
    "\n",
    "        res = 1\n",
    "      \n",
    "        l = 0\n",
    "        \n",
    "\n",
    "\n",
    "        for r in range(1, len(nums)):\n",
    "            if nums[r] <= nums[l] + n - 1:\n",
    "                \n",
    "                res = max(res,r - l + 1)\n",
    "            else:\n",
    "                while l < r and nums[l] < nums[r] - n +1:\n",
    "                    l += 1\n",
    "              \n",
    "        return n - res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # nums.sort()\n",
    "\n",
    "        \n",
    "\n",
    "        # res = 1\n",
    "      \n",
    "        # l = 0\n",
    "        # n = len(nums)\n",
    "        # start = nums[l]\n",
    "        # dic = set()\n",
    "        # dic.add(start)\n",
    "        # print(dic)\n",
    "        # for r in range(1, len(nums)):\n",
    "        #     if nums[r] <= start + n - 1:\n",
    "        #         dic.add(nums[r])\n",
    "        #         res = max(res,len(dic))\n",
    "        #         print(dic)\n",
    "        #     else:\n",
    "        #         while l < r and nums[l] < nums[r] - n + 1:\n",
    "        #             dic.remove(nums[l])\n",
    "        #             l += 1\n",
    "        #         start = nums[l]\n",
    "        #         dic.add(nums[l])\n",
    "                \n",
    "        # return n - res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        arr = sorted(set(nums))\n",
    "        ans = inf\n",
    "        for i, x in enumerate(arr):\n",
    "            j = bisect_right(arr, x + n - 1)\n",
    "            ans = min(ans, n - j + i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        l = len(nums)#数组长度\n",
    "        nums = sorted(set(nums))#去重排序\n",
    "        c = l - len(nums)#排序数组,用于寻找边界内的数字数量\n",
    "        s = [nums.pop(0)]\n",
    "        res = l - 1\n",
    "        for i, n in enumerate(nums):#遍历数组\n",
    "            idx = bisect.bisect_left(s, n - l + 1)#二分寻找左边界下标\n",
    "            res = min(res, l - (i - idx + 2))#数组长度 - 已包含数字数量\n",
    "            s.append(n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        res = float('inf')\n",
    "        for l, num in enumerate(nums):  # 以每一位num作为最小值\n",
    "            r = bisect.bisect_right(nums, num + n - 1)  # 找到最大值\n",
    "            res = min(res, n - (r - l))  # 总长度-区间长度=需要弥补的个数\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        new_nums = sorted(set(nums))\n",
    "        j = 0\n",
    "\n",
    "        for i in range(len(new_nums)):\n",
    "            while j < len(new_nums) and new_nums[j] < new_nums[i] + n:\n",
    "                j += 1\n",
    "\n",
    "            count = j - i\n",
    "            ans = min(ans, n - count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        new_nums = sorted(set(nums))\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(len(new_nums)):\n",
    "            left = new_nums[i]\n",
    "            right = left + n - 1\n",
    "            j = bisect_right(new_nums, right)\n",
    "           \n",
    "            count = j - i\n",
    "            ans = min(ans, n - count)\n",
    "\n",
    "        \n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        res = inf\n",
    "        for i, e in enumerate(nums):\n",
    "            where = bisect_right(nums, e+n-1)\n",
    "            res = min(res, i + n - where)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        d = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > d-1:\n",
    "                m = max(m, j-i)\n",
    "                i += 1\n",
    "\n",
    "        if nums[n-1] - nums[i] < d:\n",
    "                m = max(m, n-i)\n",
    "        return d-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        a = sorted(set(nums))\r\n",
    "        m, left = len(a), 0\r\n",
    "        for i in range(m):\r\n",
    "            if a[i] - a[left] >= n: left += 1\r\n",
    "        return n - (m - left)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        left = 0\n",
    "        minop = n\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] + 1 > n:\n",
    "                left += 1\n",
    "            minop = min(n - (right - left + 1), minop)\n",
    "        return minop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 获得nums的长度\n",
    "        n = len(nums)\n",
    "\n",
    "        # 将nums转换为集合以去除重复项，然后对其进行排序\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        an = len(a)\n",
    "\n",
    "        # 初始化当前连续数字的数量和滑动窗口的右边界\n",
    "        cur = 0\n",
    "        r = 0\n",
    "        \n",
    "        # 使用滑动窗口方法来找到nums中的最大连续子数组\n",
    "        for l in range(an):\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\n",
    "                r += 1\n",
    "            cur = max(cur, r - l + 1)\n",
    "\n",
    "        # 返回需要操作的元素的数量\n",
    "        return n - cur\n",
    "\n",
    "# 测试\n",
    "solution = Solution()\n",
    "print(solution.minOperations([4, 2, 5, 3])) # 输出：0\n",
    "print(solution.minOperations([1, 2, 3, 5, 6])) # 输出：1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        delete = 0\n",
    "        i = 1\n",
    "        mx = 1\n",
    "        MAXN = 1e10\n",
    "        ans = MAXN+10\n",
    "        l,r = 0,1\n",
    "        n = len(nums)\n",
    "        tmp = list(set(nums))\n",
    "        tmp.sort()\n",
    "        \n",
    "        while r < len(tmp):\n",
    "            if l < r and tmp[l] < tmp[r]-n+1:\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return n-(r-l)\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 第一点 重复元素必改 改成什么样子后面决定\n",
    "        target = len(nums)-1\n",
    "        t = len(nums)-len(set(nums))\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        # 滑动窗口 找到最大的窗口\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] > target:\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return t+len(nums)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        c = l - len(nums)\n",
    "        s = [nums.pop(0)]\n",
    "        res = l - 1\n",
    "        for i, n in enumerate(nums):\n",
    "            idx = bisect.bisect_left(s, n - l + 1) #二分寻找左边界下标\n",
    "            res = min(res, l - (i - idx + 2)) #数组长度 - 已包含数字数量\n",
    "            s.append(n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 获得nums的长度\n",
    "        n = len(nums)\n",
    "\n",
    "        # 将nums转换为集合以去除重复项，然后对其进行排序\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        an = len(a)\n",
    "\n",
    "        # 初始化当前连续数字的数量和滑动窗口的右边界\n",
    "        cur = 0\n",
    "        r = 0\n",
    "        \n",
    "        # 使用滑动窗口方法来找到nums中的最大连续子数组\n",
    "        for l in range(an):\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\n",
    "                r += 1\n",
    "            cur = max(cur, r - l + 1)\n",
    "\n",
    "        # 返回需要操作的元素的数量\n",
    "        return n - cur\n",
    "\n",
    "# 测试\n",
    "solution = Solution()\n",
    "print(solution.minOperations([4, 2, 5, 3])) # 输出：0\n",
    "print(solution.minOperations([1, 2, 3, 5, 6])) # 输出：1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(set(nums))\n",
    "        mx = i = 0\n",
    "        for j, x in enumerate(a):\n",
    "            while a[i] <= x - n: i += 1\n",
    "            mx = max(mx, j - i + 1)\n",
    "        return n - mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        m = len(nums)\n",
    "        ans = inf\n",
    "        for i in range(m):\n",
    "            l, r = 0, i\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if nums[mid] >= nums[i] - n + 1:\n",
    "                    r = mid\n",
    "                else: l = mid + 1\n",
    "            ans = min(ans, n - (i - l + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        s = [nums.pop(0)]\n",
    "        res = n - 1\n",
    "        for i, num in enumerate(nums):\n",
    "            idx = bisect_left(s, num - n + 1)\n",
    "            res = min(res, n - (i - idx + 2))\n",
    "            s.append(num)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        temp=list(set(nums))\n",
    "        target=len(nums)-1\n",
    "        t=len(nums)-len(temp)\n",
    "        temp.sort()\n",
    "        n=len(temp)-1\n",
    "        ans=0\n",
    "        l=0\n",
    "        for r in range(n+1):\n",
    "            while temp[r]-temp[l]>=target+1:\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return t+n+1-ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        arr = []\n",
    "        res = float('inf')\n",
    "        for i, num in enumerate(nums):  # 以每一位num作为最大值\n",
    "            l = bisect.bisect_left(arr, num - n + 1)  # 二分查找最小值\n",
    "            res = min(res, n - (i - l + 1))\n",
    "            arr.append(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        max_diff=n-1\n",
    "        nums=list(set(nums))\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        m=len(nums)\n",
    "        left=0\n",
    "        res=inf\n",
    "        if n==1:\n",
    "            return 0\n",
    "        for right in range(1,m):\n",
    "            while nums[right]>nums[left]+max_diff and right>left:\n",
    "                left+=1\n",
    "            res=min(res,n-(right-left+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        L = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        r = 0\n",
    "        res = L\n",
    "        for i,n in enumerate(nums):\n",
    "            while r<len(nums) and nums[r]<n+L:\n",
    "                r += 1\n",
    "            res = min(res, L-(r-i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        m = len(nums)\n",
    "        for i in range(m):\n",
    "            if n - i < ans:\n",
    "                return  n - ans\n",
    "            num = nums[i] + n - 1\n",
    "            r = bisect.bisect(nums,num)\n",
    "            if r < m and nums[r] != num or r == m:\n",
    "                ans = max(ans, r - i)\n",
    "            else:\n",
    "                ans = max(ans, r - i + 1)\n",
    "        return n - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        seen = set()\n",
    "        for i, v in enumerate(nums):\n",
    "            if v not in seen:\n",
    "                seen.add(v)\n",
    "            else:\n",
    "                nums[i] = inf\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        j = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            while j < n and nums[j] < v + n:\n",
    "                j += 1\n",
    "            if (s := n - (j - i)) < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "\n",
    "        if nums[n-1] - nums[i] < n:\n",
    "                m = max(m, len(d))\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "\n",
    "        if nums[n-1] - nums[i] < n:\n",
    "                m = max(m, len(d))\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            if j == n-1 and nums[j] - nums[i] < n:\n",
    "                m = max(m, len(set(nums[i:])))\n",
    "\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "            if j == n-1 and nums[j] - nums[i] < n:\n",
    "                m = max(m, len(d))\n",
    "\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        countm,counts=1,0      \n",
    "        nums=sorted(nums)\n",
    "        nums.append(0)\n",
    "        for i in range(len(nums)-1):\n",
    "            if (nums[i] == nums[i + 1]):\n",
    "                countm += 1\n",
    "            elif (countm == 1):\n",
    "                return -1\n",
    "            else:\n",
    "                if (countm % 3 == 0):\n",
    "                    counts += countm // 3\n",
    "                else:\n",
    "                    counts += countm // 3 + 1\n",
    "                countm = 1\n",
    "        return counts\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=1\n",
    "        count=0      \n",
    "        nums.sort()\n",
    "        nums.append(0)\n",
    "        for i in range(len(nums)-1):\n",
    "            if (nums[i] == nums[i + 1]):\n",
    "                n += 1\n",
    "            elif (n== 1):\n",
    "                return -1\n",
    "            else:\n",
    "                if (n% 3 == 0):\n",
    "                    count +=n// 3\n",
    "                else:\n",
    "                    count +=n// 3 + 1\n",
    "                n= 1\n",
    "        return count\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a = dict()\n",
    "        for i in nums:\n",
    "            if i in a:\n",
    "                a[i] += 1\n",
    "            else:\n",
    "                a[i] = 1\n",
    "        ans = 0\n",
    "        for i in a.keys():\n",
    "            p = a[i]\n",
    "            if p == 1: return -1\n",
    "            if p % 3 == 0: ans += p // 3\n",
    "            else: \n",
    "                ans += p // 3 + 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        li=Counter(nums)\n",
    "        re=0\n",
    "        for index,val in li.items():\n",
    "            if val==1:\n",
    "                return -1\n",
    "            if val%3==0:\n",
    "                re+=val//3\n",
    "            else:\n",
    "                re+=val//3+1\n",
    "        return re\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        ans = 0\n",
    "        for x, y in cnt.items():\n",
    "            if y < 2:\n",
    "                return -1\n",
    "            if y % 3 == 0:\n",
    "                ans += y // 3\n",
    "            elif y % 3 == 1:\n",
    "                ans += (y // 3 - 1) + 2\n",
    "            elif y % 3 == 2:\n",
    "                ans += y // 3 + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        if 1 in cnt.values():\n",
    "            return -1\n",
    "        return sum((c + 2) // 3 for c in cnt.values())\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 先排序\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        # 二分找到left_idx最右侧位置，right_idx-left_idx分奇偶计算次数\n",
    "        left_idx = 0\n",
    "        res = 0\n",
    "        while left_idx < len(nums):\n",
    "            right_idx = bisect.bisect_right(nums, nums[left_idx])\n",
    "            # print(res, left_idx, right_idx)\n",
    "\n",
    "            if right_idx - left_idx == 1:\n",
    "                return -1\n",
    "            elif right_idx - left_idx == 2:\n",
    "                res += 1\n",
    "            elif (right_idx - left_idx) % 3 == 0:\n",
    "                res += (right_idx-left_idx) // 3\n",
    "                # print(res)\n",
    "            elif (right_idx - left_idx) % 3 == 1:\n",
    "                res += (right_idx - left_idx) // 3 - 1 + 2\n",
    "            else:\n",
    "                res += (right_idx - left_idx) // 3 + 1\n",
    "            \n",
    "            left_idx = right_idx\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        result = 0\n",
    "        for v in mapping.values():\n",
    "            q, r = v//2, v%2\n",
    "            if(q < r):\n",
    "                return -1\n",
    "            result += v//3 if v%3==0 else v//3+1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        result = 0\n",
    "        for v in mapping.values():\n",
    "            q, r = v//2, v%2\n",
    "            if(q < r):\n",
    "                return -1\n",
    "            result += v//3 if v%3==0 else v//3+1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a = dict()\n",
    "        for x in nums:\n",
    "            if x in a:\n",
    "                a[x] += 1\n",
    "            else:\n",
    "                a[x] = 1\n",
    "        val = 0\n",
    "        for v in a.values():\n",
    "            if v > 1:\n",
    "                val += v // 3\n",
    "                if v % 3 != 0:\n",
    "                    val+=1\n",
    "            else:\n",
    "                return -1\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        res = Counter(nums).items()\n",
    "        ans = 0\n",
    "        for k,v in res:\n",
    "            if v==1:\n",
    "                return -1\n",
    "            elif v%3==0:\n",
    "                ans+= v//3\n",
    "            elif v%3==1:\n",
    "                ans+= (v-4)//3+2\n",
    "            elif v%3==2:\n",
    "                ans+= v//3+1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        for key, val in cnt.items():\n",
    "            if val == 1:\n",
    "                return -1\n",
    "            if val % 3 == 1:\n",
    "                ans += val//3+1\n",
    "            elif val % 3 == 2:\n",
    "                ans += val//3+1\n",
    "            else:\n",
    "                ans += val//3\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            if v == 1:\n",
    "                return -1\n",
    "            if v % 3 == 0:\n",
    "                ans += v // 3\n",
    "            else:\n",
    "                ans += v // 3 + 1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        dic = Counter(nums)\n",
    "        count = 0\n",
    "        if 1 in dic.values():\n",
    "            return -1\n",
    "        for i in dic.values():\n",
    "           count += (i+2)//3\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        counter = Counter(nums)\n",
    "        res = 0\n",
    "        for v in counter.values():\n",
    "            c1, c2, ok = splitToKAndKPlusOne(v, 2)\n",
    "            if not ok:\n",
    "                return -1\n",
    "            res += c1 + c2\n",
    "        return res\n",
    "\n",
    "def splitToKAndKPlusOne(num: int, k: int, minimize=True) -> Tuple[int, int, bool]:\n",
    "    \"\"\"将 num 拆分成 k 和 k+1 的和，使得拆分的个数最(多/少).\n",
    "\n",
    "    Args:\n",
    "        num (int): 正整数.\n",
    "        k (int): 正整数.\n",
    "        minimize (bool, optional): 是否使得拆分的个数最少. 默认为最少(true).\n",
    "\n",
    "    Returns:\n",
    "        Tuple[int, int, bool]: count1和count2分别是拆分成k和k+1的个数，ok表示是否可以拆分.\n",
    "    \"\"\"\n",
    "    if minimize:\n",
    "        count2 = (num + k) // (k + 1)\n",
    "        diff = (k + 1) * count2 - num\n",
    "        if diff > count2:\n",
    "            return 0, 0, False\n",
    "        return diff, count2 - diff, True\n",
    "    count1 = num // k\n",
    "    diff = num - k * count1\n",
    "    if diff > count1:\n",
    "        return 0, 0, False\n",
    "    return count1 - diff, diff, True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        map = {}\n",
    "        for i in range(len(nums)):\n",
    "            map[nums[i]] = map.get(nums[i], 0) + 1\n",
    "        count = 0\n",
    "        for val in map.values():\n",
    "            if val == 1:\n",
    "                return -1\n",
    "            if val % 3 == 0:\n",
    "                count += val // 3\n",
    "            elif val % 3 == 2:\n",
    "                count += (val - 2) // 3 + 1\n",
    "            else:\n",
    "                count += (val - 4) // 3 + 2\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "# 找1000以内的质数\n",
    "P = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        P.append(i)\n",
    "        for j in range(i*i, MX, i):\n",
    "            is_prime[j] = False\n",
    "# print(P)\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        # print(cnt.values())\n",
    "        ans = 0\n",
    "        for k,v in cnt.items():\n",
    "            if v <= 1:\n",
    "                return -1\n",
    "        global P\n",
    "        P = set(P)\n",
    "        # print(P)\n",
    "        for k,v in cnt.items():\n",
    "            while v % 3 != 0:\n",
    "                ans += 1\n",
    "                v -= 2\n",
    "            ans += v //3\n",
    "            # print(v)\n",
    "            \n",
    "            # while v in P:\n",
    "            #     print(v)\n",
    "            #     if v == 3:\n",
    "            #         ans += 1\n",
    "            #         break\n",
    "            #     elif v == 2:\n",
    "            #         ans += 1\n",
    "            #         break\n",
    "            #     v -= 2\n",
    "            #     ans += 1\n",
    "            # # print(v)\n",
    "            # while v%3 != 0:\n",
    "            #     v -= 2\n",
    "            #     ans += 1\n",
    "            # if v %3 == 0:\n",
    "            #     ans += v//3\n",
    "            # elif v%2== 0:\n",
    "            #     ans += v//2\n",
    "        return ans \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        for item in nums:\n",
    "            if dp.get(item) == None:\n",
    "                dp[item] = 0\n",
    "            dp[item] += 1\n",
    "        ans = 0\n",
    "        for item in dp:\n",
    "            print(item, dp.get(item))\n",
    "            if dp.get(item) == 1:\n",
    "                return -1\n",
    "            now = dp.get(item)\n",
    "            ans += (now // 6) * 2\n",
    "            now = now % 6\n",
    "            if now >= 1 and now <= 3:\n",
    "                ans += 1\n",
    "            elif now >= 4:\n",
    "                ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        for item in nums:\n",
    "            if dp.get(item) == None:\n",
    "                dp[item] = 0\n",
    "            dp[item] += 1\n",
    "        ans = 0\n",
    "        for item in dp:\n",
    "            print(item, dp.get(item))\n",
    "            if dp.get(item) == 1:\n",
    "                return -1\n",
    "            now = dp.get(item)\n",
    "            ans += (now // 6) * 2\n",
    "            now = now % 6\n",
    "            if now >= 1 and now <= 3:\n",
    "                ans += 1\n",
    "            elif now >= 4:\n",
    "                ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans =0\n",
    "        d=Counter(nums)\n",
    "        for v in d.values():\n",
    "            if v==1:\n",
    "                return -1 \n",
    "            ans +=(v+2)//3\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        diction = {}\n",
    "        ret = 0\n",
    "        for i in nums:\n",
    "            if i in diction:\n",
    "                diction[i] += 1\n",
    "            else:\n",
    "                diction[i] = 1\n",
    "        for count in diction.values():\n",
    "            print(count)\n",
    "            if count < 2:\n",
    "                return -1\n",
    "            if count % 3 == 0:\n",
    "                ret += count // 3\n",
    "            elif count % 3 == 2:\n",
    "                ret += count // 3 + 1\n",
    "            elif count % 3 == 1:\n",
    "                ret += count // 3 + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt=collections.Counter(nums)\n",
    "        ans=0\n",
    "        for x in cnt:\n",
    "            if cnt[x]<2:\n",
    "                return -1\n",
    "            ans=ans+cnt[x]//3+int(cnt[x]%3!=0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for freq in Counter(nums).values():\n",
    "            if freq == 1:\n",
    "                return -1\n",
    "            ans += freq // 3 + bool(freq % 3)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def judge_number(self, number):\n",
    "        if number % 3 == 0:\n",
    "            return number // 3\n",
    "        elif number == 1:\n",
    "            return -1\n",
    "        else:\n",
    "            temp_min = float('inf')\n",
    "            for i in range(0, number // 3 + 1):\n",
    "                if (number - i * 3) % 2 == 0:\n",
    "                    temp_min = min(i + (number - i * 3) // 2, temp_min)\n",
    "            return temp_min\n",
    "            \n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        dic = collections.Counter(nums)\n",
    "        count = 0\n",
    "        for e in dic.values():\n",
    "            if self.judge_number(e) == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                count += self.judge_number(e)\n",
    "\n",
    "        return count\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums = Counter(nums)\n",
    "        for x, c in nums.items():\n",
    "            if c % 3 == 0:\n",
    "                ans += c // 3\n",
    "                nums[x] = 0\n",
    "            else:\n",
    "                k3 = max(0, (c + (2 if c % 3 == 2 else 0)) // 3 - 1)\n",
    "                k2 = (c - k3 * 3) // 2\n",
    "                ans += k2 + k3\n",
    "                nums[x] -= k3 * 3 + k2 * 2\n",
    "        return (ans if sum(c for c in nums.values()) == 0 else -1)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteCount(self, num: int) -> int:\n",
    "        dp = [0 for i in range(num + 1)]\n",
    "        if num < 2:\n",
    "            return 0\n",
    "        elif num == 2:\n",
    "            return 1\n",
    "        else:\n",
    "            dp[2] = 1\n",
    "            dp[3] = 1\n",
    "        for i in range(4, num + 1):\n",
    "            if dp[i - 2] == 0 and dp[i - 3] == 0:\n",
    "                dp[i] = 0\n",
    "            elif dp[i - 2] == 0:\n",
    "                dp[i] = dp[i - 3] + 1\n",
    "            elif dp[i - 3] == 0:\n",
    "                dp[i] = dp[i - 2] + 1\n",
    "            else:\n",
    "                dp[i] = min(dp[i - 2], dp[i - 3]) + 1\n",
    "        return dp[num]\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        record = Counter(nums)\n",
    "        res = 0\n",
    "        for num in record.keys():\n",
    "            value = record[num]\n",
    "            count = self.deleteCount(value)\n",
    "            if count == 0:\n",
    "                return -1\n",
    "            else:\n",
    "                res += count\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        hashtab = Counter(nums)\n",
    "        nums = set(nums)\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            if hashtab[i] == 1:\n",
    "                return -1\n",
    "            if hashtab[i] % 3 == 0:\n",
    "                ans += hashtab[i] // 3\n",
    "            else:\n",
    "                ans += hashtab[i] // 3 + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        #print(cnt)\n",
    "        ans = 0\n",
    "        is_d = 0\n",
    "        for j in cnt.values():\n",
    "\n",
    "            # 其实就是脑筋急转弯, 除3余1的时候单独考虑就行了.\n",
    "            if j%3 == 1: \n",
    "                j = j-2\n",
    "                three = j//3\n",
    "                two = (j-three*3)//2\n",
    "                ans += three +two +1\n",
    "                if j >= 0:\n",
    "                    is_d += 1\n",
    "            else:\n",
    "                three = j//3\n",
    "                two = (j-three*3)//2\n",
    "                ans += three +two \n",
    "                is_d += 1            \n",
    "\n",
    "\n",
    "\n",
    "        if is_d == len(set(nums)):\n",
    "            return ans\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums_counter = Counter(nums)\n",
    "        answer = 0 \n",
    "        for value in nums_counter.values():\n",
    "            if value == 1:\n",
    "                return -1 \n",
    "            else:\n",
    "                if value % 3 == 1:\n",
    "                    answer += value // 3 - 1 + 2 \n",
    "                elif value % 3 == 2:\n",
    "                    answer += value // 3 + 1 \n",
    "                else:\n",
    "                    answer += value // 3 \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        dic = defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]]+=1\n",
    "        for num in set(nums):\n",
    "            tmp = dic[num]\n",
    "            if tmp == 1:\n",
    "                return -1\n",
    "            if tmp % 3 == 1:\n",
    "                ans+=(tmp//3)+1\n",
    "\n",
    "            else:\n",
    "                ans+=tmp//3 + int(tmp % 3 == 2)\n",
    "            #print(num,ans)\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        #print(cnt)\n",
    "        ans = 0\n",
    "        is_d = 0\n",
    "        for j in cnt.values():\n",
    "\n",
    "            if j%3 == 1: \n",
    "                j = j-2\n",
    "                three = j//3\n",
    "                two = (j-three*3)//2\n",
    "                ans += three +two +1\n",
    "                if j >= 0:\n",
    "                    is_d += 1\n",
    "            else:\n",
    "                three = j//3\n",
    "                two = (j-three*3)//2\n",
    "                ans += three +two \n",
    "                is_d += 1            \n",
    "\n",
    "\n",
    "\n",
    "        if is_d == len(set(nums)):\n",
    "            return ans\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums_counter = Counter(nums)\n",
    "        answer = 0 \n",
    "        for value in nums_counter.values():\n",
    "            if value == 1:\n",
    "                return -1 \n",
    "            else:\n",
    "                if value % 3 == 1:\n",
    "                    answer += value // 3 - 1 + 2 \n",
    "                elif value % 3 == 2:\n",
    "                    answer += value // 3 + 1 \n",
    "                else:\n",
    "                    answer += value // 3 \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心 + 分类讨论 + 简洁写法\n",
    "    # https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-empty/solutions/2464673/tan-xin-jian-ji-xie-fa-pythonjavacgo-by-ziiin/\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        if 1 in cnt.values():\n",
    "            return -1\n",
    "\n",
    "        return sum((c + 2) // 3 for c in cnt.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnts = Counter(nums)\n",
    "        ans = 0\n",
    "        for v in cnts.values():\n",
    "            if v == 1: return -1\n",
    "            ans += ceil(v / 3)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minOperations(self, nums):\n",
    "\t\td=dict()\n",
    "\t\tfor n in nums:\n",
    "\t\t\td[n]=d.get(n,0)+1\n",
    "\t\tans=0\n",
    "\t\tfor k in d:\n",
    "\t\t\tif d[k]==1:\n",
    "\t\t\t\treturn -1\n",
    "\t\t\tif d[k]%3==0:\n",
    "\t\t\t\tans+=d[k]//3\n",
    "\t\t\telif (d[k]-2)%3==0:\n",
    "\t\t\t\tans+=1+(d[k]-2)//3\n",
    "\t\t\telse:\n",
    "\t\t\t\tans+=2+(d[k]-4)//3\n",
    "\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = collections.Counter(nums)\n",
    "        def get(x):\n",
    "            res = 0\n",
    "            if x & 1:\n",
    "                res += 1\n",
    "                x -= 3\n",
    "            cnt = x // 2\n",
    "            t = cnt % 3\n",
    "            cnt //= 3\n",
    "            cnt *= 2\n",
    "            # print(cnt, t, res)\n",
    "            return cnt + t + res\n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            if v == 1:\n",
    "                return -1\n",
    "            # print(k, v, get(v))\n",
    "            ans += get(v)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def min_2_or_3_count(n):\n",
    "            count_2 = 0\n",
    "            count_3 = 0\n",
    "            while n % 3 != 0:\n",
    "                if n == 4:\n",
    "                    count_2 += 2\n",
    "                    n = 0\n",
    "                    break\n",
    "                if n % 3 == 2:\n",
    "                    n -= 2\n",
    "                    count_2 += 1\n",
    "                elif n % 3 == 1:\n",
    "                    n -= 3\n",
    "                    count_3 += 1\n",
    "            count_3 += n // 3\n",
    "            return count_2+count_3\n",
    "        cnt = Counter(nums)\n",
    "        res = 0\n",
    "        for _, v in cnt.items():\n",
    "            if v == 1:\n",
    "                return -1\n",
    "            else:\n",
    "                res += min_2_or_3_count(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        print(cnt)\n",
    "        if 1 in cnt.values():\n",
    "            return -1\n",
    "        return sum((c + 2) // 3 for c in cnt.values())\n",
    "        # import collections\n",
    "        # a = collections.Counter(nums)\n",
    "        # print(a)\n",
    "        # count = 0\n",
    "        # for k,v in enumerate(a):\n",
    "        #     print(a[v])\n",
    "        #     if a[v] % 2 == 0:\n",
    "        #         a1 = a[v] // 2\n",
    "        #         count = count + a1\n",
    "        #     elif a[v] % 3 == 0: \n",
    "        #         a1 = a[v] // 3\n",
    "        #         count = count + a1\n",
    "        #     else:\n",
    "        #         return -1\n",
    "        # return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        c, res = collections.Counter(nums), 0\n",
    "        for n in c.values():\n",
    "            if n==1: return -1\n",
    "            elif n%3==1: res += n//3+1\n",
    "            else: res += (n+1)//3\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        print(cnt)\n",
    "        if 1 in cnt.values():\n",
    "            return -1\n",
    "        return sum((c + 2) // 3 for c in cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        # print(cnt)\n",
    "        # 1. 对三取余 剩下0 正好可以被三整除\n",
    "        # 2. 对三取余剩下1 比如4=2+2, 7=1 * 3 + 2 + 2, 10 = 2 * 3 + 2 + 2, 13 = 3*3 + 2 + 2\n",
    "        # 3. 对三取余剩下2 比如5=1*3+2, 8=2*3+2, 11=3*3+2, 2\n",
    "        # 4. 为1不可以删除\n",
    "        ans = 0\n",
    "        print(cnt)\n",
    "        for k, v in cnt.items():\n",
    "            if v == 1:\n",
    "                return -1\n",
    "            elif v % 3 == 0:\n",
    "                ans += (v // 3)\n",
    "            elif v % 3 == 1:\n",
    "                ans += ((v - 4) // 3 + 2)\n",
    "            elif v % 3 == 2:\n",
    "                ans += (v // 3 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        d=defaultdict(int)\n",
    "        n_s=set()\n",
    "        for n in nums:\n",
    "            n_s.add(n)\n",
    "            d[n]+=1\n",
    "            \n",
    "        ans=0\n",
    "        for n in list(n_s):\n",
    "            r3=d[n]//3\n",
    "            re=d[n]%3\n",
    "            if re==1 and not r3:\n",
    "                return -1\n",
    "            ans+=r3\n",
    "            ans+=1 if re else 0\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "            lstbox = list(boxes)\n",
    "            if '1' not in lstbox:\n",
    "                return [0 for _ in range(len(lstbox))]\n",
    "            else:\n",
    "                res = []\n",
    "                i,j =0,1\n",
    "                while i < len(lstbox):\n",
    "                    count = 0\n",
    "                    while j < len(lstbox):\n",
    "\n",
    "                        if lstbox[j] =='1':\n",
    "                            count += abs(j-i)\n",
    "                        j+=1\n",
    "                    i += 1\n",
    "                    j = 0\n",
    "                    res.append(count)\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        def acc(box_list):\n",
    "            n = len(box_list)\n",
    "            l = [[0, 0] for _ in range(n)]\n",
    "            for i in range(0, n):\n",
    "                moves, count = l[i-1]\n",
    "                l[i] = [moves + count, count + int(box_list[i])]\n",
    "              \n",
    "            return l\n",
    "\n",
    "        l, r = acc(boxes), reversed(acc(boxes[::-1]))\n",
    "       \n",
    "        return [a[0]+b[0] for a,b in zip(l,r)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = [0] * len(boxes)\n",
    "        n = len(boxes)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if boxes[j] == '1':\n",
    "                    ans[i] += abs(j-i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        #将某个位置左边和右边的小球距离的相加\n",
    "        #暴力法时间复杂度为n**2\n",
    "        n = len(boxes)\n",
    "        \n",
    "        res = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            #判断当前位置的左边和右边\n",
    "            tmp = 0\n",
    "            #判断左边\n",
    "            for j in range(0, i):\n",
    "                if boxes[j] == '1':\n",
    "                    tmp += i-j\n",
    "            #判断右边\n",
    "            for j in range(i+1, n):\n",
    "                if boxes[j] == '1':\n",
    "                    tmp += j-i \n",
    "            res[i] = tmp\n",
    "        return res\n",
    "\n",
    "    #采用先判断所有位置的最左边，在判断所有位置的右边，然后将左右两边相加实现\n",
    "    #基于动态规划实现 时间复杂度为n\n",
    "    #dp[(i, j)] 记录前面有多少个1 以及 当前位置的移动步数\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        dp = [[0, 0] for i in range(n)]\n",
    "        for i in range(1, n):\n",
    "            #当前位置的移动步数等于前面的移动步数相加，同时加上1的个数\n",
    "            dp[i][1] = dp[i-1][0]+dp[i-1][1]\n",
    "            dp[i][0] = dp[i-1][0]\n",
    "            #前面一位是1 则步数加1 同时将 1的个数加1\n",
    "            if boxes[i-1] == '1':\n",
    "                dp[i][0] += 1\n",
    "                dp[i][1] += 1\n",
    "        print(dp)\n",
    "        #执行右到左\n",
    "        dp2 = [[0, 0] for i in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp2[i][1] = dp2[i+1][0] + dp2[i+1][1]\n",
    "            dp2[i][0] = dp2[i+1][0]\n",
    "            if boxes[i+1] == '1':\n",
    "                dp2[i][0] += 1\n",
    "                dp2[i][1] += 1\n",
    "        print(dp2)\n",
    "        res = []\n",
    "        for l, r in zip(dp, dp2):\n",
    "            res.append(l[1]+r[1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = [0] * len(boxes)\n",
    "        i = 0\n",
    "        j = len(boxes) - 1\n",
    "        k = 0\n",
    "        for i in range(len(boxes)):\n",
    "            while j > i:\n",
    "                if int(boxes[j]):\n",
    "                    ans[i] += j - i\n",
    "                j -= 1\n",
    "            j = len(boxes) - 1\n",
    "            while i > k:\n",
    "                if int(boxes[k]):\n",
    "                    ans[i] += i - k\n",
    "                k += 1\n",
    "            k = 0\n",
    "        return ans\n",
    "            \n",
    "                 \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        dl=dict()\n",
    "        dr=dict()\n",
    "        dl[0]=0\n",
    "        dr[len(boxes)-1]=0\n",
    "        if boxes[0]=='0':\n",
    "            cnt=0\n",
    "        else:\n",
    "            cnt=1\n",
    "        for pos in range(1,len(boxes)):\n",
    "            dl[pos]=cnt\n",
    "            if boxes[pos]=='1':\n",
    "                cnt+=1\n",
    "        if boxes[-1]=='0':\n",
    "            cnt=0\n",
    "        else:\n",
    "            cnt=1\n",
    "        for pos in range(len(boxes)-2,-1,-1):\n",
    "            dr[pos]=cnt\n",
    "            if boxes[pos]=='1':\n",
    "                cnt+=1    \n",
    "        a=[]\n",
    "        cnt=0\n",
    "        for pos in range(1,len(boxes)):\n",
    "            if boxes[pos]=='1':\n",
    "                cnt+=pos\n",
    "        a.append([0,cnt])\n",
    "        for pos in range(1,len(boxes)):\n",
    "            plcnt=a[pos-1][0]\n",
    "            prcnt=a[pos-1][1]\n",
    "            lcnt=plcnt+dl[pos]\n",
    "            rcnt=prcnt-dr[pos]\n",
    "            if boxes[pos]=='1':\n",
    "                rcnt-=1\n",
    "            a.append([lcnt,rcnt])\n",
    "        b=[]\n",
    "        for e in a:\n",
    "            b.append(sum(e))\n",
    "        return b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = [0] * len(boxes)\n",
    "        \n",
    "        \n",
    "        for i in range(len(boxes)):\n",
    "            if boxes[i] == '1':\n",
    "                left = i - 1\n",
    "                right = i + 1\n",
    "                step = 1\n",
    "                while left >= 0 or right < len(boxes):\n",
    "                    if left >= 0:\n",
    "                        res[left] += step\n",
    "                        left -= 1\n",
    "                    \n",
    "                    if right < len(boxes):\n",
    "                        res[right] += step\n",
    "                        right += 1\n",
    "                    \n",
    "                    step += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        boxes_list = list(boxes)\n",
    "        answer = [0]*len(boxes_list)\n",
    "        for i in range(0,len(boxes_list)):\n",
    "            for j in range(0,len(boxes_list)):\n",
    "                if boxes_list[j] == \"1\":\n",
    "                    answer[i] += abs(i-j)\n",
    "        return (answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        length = len(boxes)\n",
    "        c1, c2, pre, suf = Counter(), Counter(), Counter(), Counter()\n",
    "        for i in range(length):\n",
    "            c1[i] = c1[i - 1] + (1 if boxes[i] == '1' else 0)\n",
    "            c2[length - i - 1] = c2[length - i] + (1 if boxes[length - i - 1] == '1' else 0)\n",
    "            pre[i] = pre[i - 1] + c1[i - 1]\n",
    "            suf[length - i - 1] = suf[length - i] + c2[length - i]\n",
    "        return [pre[i] + suf[i] for i in range(length)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        l = boxes.__len__()\n",
    "        ans = [0] * l\n",
    "        pre, cnt = 0, 0\n",
    "        for i in range(1, l):\n",
    "            if boxes[i-1] == \"1\":\n",
    "                cnt += 1\n",
    "            ans[i] = pre + cnt\n",
    "            pre += cnt\n",
    "        pre, cnt = 0, 0\n",
    "        for i in range(l-2, -1, -1):\n",
    "            if boxes[i+1] ==\"1\":\n",
    "                cnt += 1\n",
    "            ans[i] += pre + cnt\n",
    "            pre += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(boxes)\n",
    "        for i in range(n):\n",
    "            s=0\n",
    "            for j,c in enumerate(boxes):\n",
    "                if c=='1':\n",
    "                    s += abs(j-i)\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        result = []\n",
    "        for i in range (len(boxes)):\n",
    "            length = 0\n",
    "            for j in range (len(boxes)):\n",
    "                if boxes[j] == '1':\n",
    "                    length += abs(j - i)\n",
    "            result.append(length)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        ans = [0] * n\n",
    "        pre, sub = int(boxes[0]), 0\n",
    "        for i in range(1, n):\n",
    "            if boxes[i] == '1':\n",
    "                sub += 1\n",
    "                ans[0] += i\n",
    "        for i in range(1, n):\n",
    "            ans[i] = ans[i - 1] + pre - sub\n",
    "            if boxes[i] == '1':\n",
    "                sub -= 1\n",
    "                pre += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            s = sum(abs(j - i) for j, c in enumerate(boxes) if c == '1')\n",
    "            res.append(s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n=len(boxes)\n",
    "        a=[]\n",
    "        for i in range(n):\n",
    "            ans=0\n",
    "            for j in range(n):\n",
    "                if boxes[j]=='1':\n",
    "                   ans=ans+abs(j-i)\n",
    "\n",
    "            a.append(ans)\n",
    "        \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res=[]\n",
    "        for i in boxes:\n",
    "            res.append(int(i))\n",
    "        length=len(res)\n",
    "        a=[0]*length\n",
    "\n",
    "        for j in range(length):\n",
    "            for k in range(length):\n",
    "                if res[j]==1:\n",
    "                    a[k]+=abs(j-k)\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res=[]\n",
    "        for i in boxes:\n",
    "            res.append(int(i))\n",
    "        length=len(res)\n",
    "        a=[0]*length\n",
    "\n",
    "        for j in range(length):\n",
    "            for k in range(length):\n",
    "                if res[j]==1:\n",
    "                    a[k]+=abs(j-k)\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        return [sum(abs(j-i)*int(boxes[j]) for j in range(len(boxes))) for i in range(len(boxes))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = [0]*len(boxes)\n",
    "        for i in range(len(res)):\n",
    "            res[i] = sum([abs(j-i) for j in range(len(res)) if boxes[j]=='1'])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if boxes[j] == '1':\n",
    "                    ans[i] += abs(i - j)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = [0] * len(boxes)\n",
    "        for i in range(len(boxes)):\n",
    "            for j in range(len(boxes)):\n",
    "                if i==j:\n",
    "                    pass\n",
    "                if boxes[j] == '1':\n",
    "                    ans[i] += abs(i-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        answer = [0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j:\n",
    "                    if boxes[j] == '1':\n",
    "                        answer[i] = answer[i] + abs(j - i)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            tmp = 0\n",
    "            for j in range(len(boxes)):\n",
    "                if boxes[j] == '1' and j!=i:\n",
    "                    tmp += abs(j-i)\n",
    "            res.append(tmp)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        # 也就是计算元素1的下标到移动目的地下标的距离\n",
    "        n = len(boxes)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            dis = 0\n",
    "            for j in range(n):\n",
    "                if boxes[j] == \"1\":\n",
    "                    dis += abs(j-i)\n",
    "            res.append(dis)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        boxes=[int(_) for _ in boxes]\n",
    "        length = len(boxes)\n",
    "        res = [0] * length\n",
    "        right_num = 0\n",
    "        for i in range(length):\n",
    "            if boxes[i] == 1:\n",
    "                res[0] += i\n",
    "                right_num += 1\n",
    "        if boxes[0]==1:\n",
    "            right_num -= 1 #右侧1的数量\n",
    "        left_num = 0 \n",
    "        right_count = res[0]  # 右距离和\n",
    "        left_count = 0\n",
    "        \"\"\"\n",
    "        [j-1]left_count + [j] left_num = [j] left_count\n",
    "        [j-1]right_count - [j-1] right_num = [j] right _count\n",
    "        [j] res = [j] left_count + [j] right _count\n",
    "        \"\"\"\n",
    "        for j in range(1, length):\n",
    "            if boxes[j - 1] == 1:\n",
    "                left_num += 1\n",
    "            left_count += left_num\n",
    "            right_count -= right_num\n",
    "            res[j] = right_count + left_count\n",
    "            if boxes[j] == 1:\n",
    "                right_num -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            for j,b in enumerate(boxes):\n",
    "                if b == '1':\n",
    "                    ans[i] += abs(j-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans=[]\n",
    "        for i in range(len(boxes)):\n",
    "            c=0\n",
    "            for j in range(len(boxes)):\n",
    "                c+=int(boxes[j])*abs(i-j)\n",
    "            ans.append(c)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = [0] * len(boxes)\n",
    "        for i in range(len(boxes)):\n",
    "            pre = sum(i-j for j in range(0, i) if boxes[j] == \"1\")\n",
    "            post= sum(j-i for j in range(i, len(boxes)) if boxes[j] == \"1\")\n",
    "            ans[i] = pre + post\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        balls = sum(1 if i == '1' else 0 for i in boxes)\n",
    "        balls_left = 0\n",
    "        balls_right = balls - ( 1 if boxes[0]  == '1' else 0)\n",
    "        steps = sum(i if k == '1' else 0 for i,k in enumerate(boxes))\n",
    "        ans = []\n",
    "        ans.append(steps)\n",
    "        for i in range(0, len(boxes)-1):\n",
    "            # print(\"left:\",balls_left)\n",
    "            # print(\"right:\", balls_right)\n",
    "            # print(steps)\n",
    "            balls_left += 1  if boxes[i] == '1' else 0\n",
    "            steps = steps + balls_left - balls_right\n",
    "            balls_right -= 1 if i+1<len(boxes) and boxes[i+1]=='1' else 0\n",
    "            ans.append(steps)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        left, right, operations = int(boxes[0]), 0, 0\n",
    "        n = len(boxes)\n",
    "        for i in range(1, n):\n",
    "            if boxes[i] == '1':\n",
    "                right += 1\n",
    "                operations += i\n",
    "        res = [operations]\n",
    "        for j in range(1, n):\n",
    "            operations += left - right\n",
    "            if boxes[j] == \"1\":\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            res.append(operations)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        boxes=[int(_) for _ in boxes]\n",
    "        length = len(boxes)\n",
    "        res = [0] * length\n",
    "        right_num = 0\n",
    "        for i in range(length):\n",
    "            if boxes[i] == 1:\n",
    "                res[0] += i\n",
    "                right_num += 1\n",
    "        if boxes[0]==1:\n",
    "            right_num -= 1 #右侧1的数量\n",
    "        left_num = 0 \n",
    "        right_count = res[0]  # 右距离和\n",
    "        left_count = 0\n",
    "        \"\"\"\n",
    "        [j-1]left_count + [j] left_num = [j] left_count\n",
    "        [j-1]right_count - [j-1] right_num = [j] right _count\n",
    "        [j] res = [j] left_count + [j] right _count\n",
    "        \"\"\"\n",
    "        for j in range(1, length):\n",
    "            if boxes[j - 1] == 1:\n",
    "                left_num += 1\n",
    "            left_count += left_num\n",
    "            right_count -= right_num\n",
    "            res[j] = right_count + left_count\n",
    "            if boxes[j] == 1:\n",
    "                right_num -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        \n",
    "        answer: List[int] = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            count = 0\n",
    "            for j in range(0, i):\n",
    "                if boxes[j] == '0':\n",
    "                    continue\n",
    "                else:\n",
    "                    count += i - j\n",
    "            for k in range(i + 1, n):\n",
    "                if boxes[k] == '0':\n",
    "                    continue\n",
    "                else:\n",
    "                    count += k - i\n",
    "                    \n",
    "            answer.append(count)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        \n",
    "        answer: List[int] = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            count = 0\n",
    "            for j in range(0, i):\n",
    "                if boxes[j] == '0':\n",
    "                    continue\n",
    "                else:\n",
    "                    count += i - j\n",
    "            for k in range(i + 1, n):\n",
    "                if boxes[k] == '0':\n",
    "                    continue\n",
    "                else:\n",
    "                    count += k - i\n",
    "                    \n",
    "            answer.append(count)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        # res = []\n",
    "        # for i in range(len(boxes)):\n",
    "        #     s = sum(abs(j - i) for j, c in enumerate(boxes) if c == \"1\")\n",
    "        #     res.append(s)\n",
    "        # return res\n",
    "        n = len(boxes)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            strip = 0\n",
    "            for j, ch in enumerate(boxes):\n",
    "                if ch == \"1\":\n",
    "                    strip += abs(j - i)\n",
    "            ans[i] = strip\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            temp = 0\n",
    "            for j in range(i+1,n):\n",
    "                if boxes[j] == '1':\n",
    "                    temp+=j-i\n",
    "            for k in range(i-1,-1,-1):\n",
    "                if boxes[k] == '1':\n",
    "                    temp+=i-k\n",
    "            res.append(temp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        l=0\n",
    "        r=boxes.count(\"1\")\n",
    "        n=len(boxes)\n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            if boxes[i]==\"1\":\n",
    "                ans[0]+=i\n",
    "        for i in range(1,n):\n",
    "            if boxes[i-1]==\"1\":\n",
    "                r-=1\n",
    "                l+=1\n",
    "            ans[i]=ans[i-1]-r+l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        dp = [0] * n\n",
    "        left = right = 0\n",
    "\n",
    "        for i in range(n): \n",
    "            if boxes[i] == '1':\n",
    "                dp[0] += i\n",
    "                right += 1\n",
    "        \n",
    "        for j in range(1, n):\n",
    "            if boxes[j-1] == '1':\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            dp[j] = dp[j-1] - right + left\n",
    "\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        result=[]\n",
    "        for i in range(len(boxes)):\n",
    "            step=0\n",
    "            for j in range(len(boxes)):\n",
    "                if boxes[j] != '0':\n",
    "                    step+=abs(j-i)\n",
    "            result.append(step)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            temp = 0\n",
    "            for j in range(i+1,n):\n",
    "                if boxes[j] == '1':\n",
    "                    temp+=j-i\n",
    "            for k in range(i-1,-1,-1):\n",
    "                if boxes[k] == '1':\n",
    "                    temp+=i-k\n",
    "            res.append(temp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            res = 0\n",
    "            for j in range(n):\n",
    "                res += abs(j-i)*int(boxes[j])\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        idxTotal = []\n",
    "        for idx in range(len(boxes)):\n",
    "            if boxes[idx] == '1':\n",
    "                idxTotal.append(idx)\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            tmp = 0\n",
    "            for j in range(len(idxTotal)): \n",
    "                tmp += abs(idxTotal[j] - i)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        num = 0\n",
    "        sum_l = []\n",
    "        sum_ = 0\n",
    "        for i in range(len(boxes)):\n",
    "            if boxes[i] == '1':\n",
    "                num += 1\n",
    "                sum_ += i\n",
    "            sum_l.append(sum_)\n",
    "        ans = []\n",
    "        l_1 = 0\n",
    "        l_d = 0\n",
    "        for i in range(len(boxes)):\n",
    "            if boxes[i] == '1':\n",
    "                l_1 += 1\n",
    "            l_d += (l_1 - 1 if boxes[i]=='1' else l_1)\n",
    "            r_d = sum_l[-1] - sum_l[i] - (num - l_1)*i\n",
    "            ans.append(l_d+r_d)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        ans = [0] * n\n",
    "        a = boxes.count('1')\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            if boxes[i] == '1':\n",
    "                t += i\n",
    "        b, pre = 0, 0\n",
    "        for i in range(n):\n",
    "            if boxes[i] == '1':\n",
    "                b += 1\n",
    "                pre += i\n",
    "                a -= 1\n",
    "                t -= i\n",
    "\n",
    "            ans[i] = i * b - pre + t - i * a\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(sum(abs(j-i) for j,c in enumerate(boxes) if c == '1'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        left, right, operations = int(boxes[0]), 0, 0\n",
    "        for i in range(1, len(boxes)):\n",
    "            if boxes[i] == '1':\n",
    "                right += 1\n",
    "                operations += i\n",
    "        res = [operations]\n",
    "        for i in range(1, len(boxes)):\n",
    "            operations += left - right\n",
    "            if boxes[i] == '1':\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            res.append(operations)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(boxes)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if boxes[j] == \"1\":\n",
    "                    cnt += abs(i - j)\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        l,r,o = int(boxes[0]),0,0\n",
    "        ans = []\n",
    "        for i in range(1,len(boxes)):\n",
    "            if boxes[i] == '1':\n",
    "                r += 1\n",
    "                o += i\n",
    "        ans.append(o)\n",
    "        for i in range(1,len(boxes)):\n",
    "            o += l-r\n",
    "            if boxes[i] == '1':\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            ans.append(o)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(boxes)\n",
    "        for i in range(0, n):\n",
    "            cnt = 0\n",
    "            for j in range(0, n):\n",
    "                if j != i and boxes[j] == '1':\n",
    "                    cnt += abs(j - i)\n",
    "            ans.append(cnt)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        N = len(boxes)\n",
    "        res = [0]*N\n",
    "\n",
    "        pre = 0\n",
    "        total = 0\n",
    "        for i in range(1,N):\n",
    "            if boxes[i-1]=='1': total+=1\n",
    "            res[i] = pre+total\n",
    "            pre+=total\n",
    "        \n",
    "\n",
    "        pre = 0\n",
    "        total = 0\n",
    "        for i in range(N-2, -1, -1):\n",
    "            if boxes[i+1]=='1': total+=1\n",
    "            res[i] += pre+total\n",
    "            pre+=total\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        # res = []\n",
    "        # for i in range(len(boxes)):\n",
    "        #     s = sum(abs(j - i) for j, c in enumerate(boxes) if c == \"1\")\n",
    "        #     res.append(s)\n",
    "        # return res\n",
    "        \n",
    "        l, r, operations = int(boxes[0]), 0, 0\n",
    "        for i in range(1, len(boxes)):\n",
    "            if boxes[i] == \"1\":\n",
    "                r += 1\n",
    "                operations += i\n",
    "        res = [operations]\n",
    "        for i in range(1, len(boxes)):\n",
    "            operations += l - r\n",
    "            if boxes[i] == \"1\":\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            res.append(operations)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            s = sum(abs(j - i) for j, c in enumerate(boxes) if c == '1')\n",
    "            res.append(s)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes):\n",
    "        \"\"\"\n",
    "        求解将所有球运送到boxes[i]的位置所需要的最少的操作数\n",
    "        Args:\n",
    "            boxes(str): 各个盒子存放球的情况\n",
    "        returns (list[int]): \n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if boxes == None or len(boxes) == 0:\n",
    "            return []\n",
    "        \n",
    "        #遍历boxes, 查找所有球所在的位置\n",
    "        n = len(boxes)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        poses = []  #存储各个球所在的位置\n",
    "\n",
    "        for i in range(n):\n",
    "            if boxes[i] == '1':\n",
    "                poses.append(i)\n",
    "\n",
    "        #依次从[0...n-1]求解所有球转移到i位置所需要的最少次数\n",
    "        for i in range(n):\n",
    "            for pos in poses:\n",
    "                #answer[i] += abs(i - pos)\n",
    "                ans[i] += abs(i - pos)\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        boxes=[int(_) for _ in boxes]\n",
    "        length = len(boxes)\n",
    "        res = [0] * length\n",
    "        right_num = 0\n",
    "        for i in range(length):\n",
    "            if boxes[i] == 1:\n",
    "                res[0] += i\n",
    "                right_num += 1\n",
    "        if boxes[0]==1:\n",
    "            right_num -= 1 #右侧1的数量\n",
    "        left_num = 0 \n",
    "        right_count = res[0]  # 右距离和\n",
    "        left_count = 0\n",
    "        \"\"\"\n",
    "        [j-1]left_count + [j] left_num = [j] left_count\n",
    "        [j-1]right_count - [j-1] right_num = [j] right _count\n",
    "        [j] res = [j] left_count + [j] right _count\n",
    "        \"\"\"\n",
    "        for j in range(1, length):\n",
    "            if boxes[j - 1] == 1:\n",
    "                left_num += 1\n",
    "            left_count += left_num\n",
    "            right_count -= right_num\n",
    "            res[j] = right_count + left_count\n",
    "            if boxes[j] == 1:\n",
    "                right_num -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        count = []\n",
    "        for i in range(len(boxes)):\n",
    "            counter=0\n",
    "            for j in range(len(boxes)):\n",
    "                \n",
    "                if j != i:\n",
    "\n",
    "                    if int(boxes[j]) == 1:\n",
    "                        diff=abs(j-i)\n",
    "\n",
    "                        counter=counter + diff\n",
    "            count.append(counter)\n",
    "                \n",
    "        return count\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        a=[]\n",
    "        for i in range(len(boxes)):\n",
    "            b=0\n",
    "            for j in range(len(boxes)):\n",
    "                if boxes[j]=='1':\n",
    "                    b+=abs(j-i)\n",
    "            a.append(b)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            s = sum(abs(j - i) for j, c in enumerate(boxes) if c == '1')\n",
    "            res.append(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        count = []\n",
    "        \n",
    "        box=[]\n",
    "        for i in range(len(boxes)):\n",
    "            box.append(int(boxes[i]))\n",
    "        for i in range(len(box)):\n",
    "            counter=0\n",
    "            for j in range(len(box)):\n",
    "                \n",
    "                if j != i:\n",
    "\n",
    "                    if box[j] == 1:\n",
    "                        diff=abs(j-i)\n",
    "\n",
    "                        counter=counter + diff\n",
    "            count.append(counter)\n",
    "                \n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        cur = 0\n",
    "        for i, c in enumerate(boxes):\n",
    "            left[i], cur = left[i - 1] + cur, cur + (c == '1')\n",
    "        cur = int(boxes[-1] == '1')\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i], cur = right[i + 1] + cur, cur + (boxes[i] == '1')\n",
    "        return [left[i] + right[i] for i in range(n)]  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> list[int]:\n",
    "        result=[]\n",
    "        L=[x for x in range(len(boxes)) if boxes[x]==\"1\"]\n",
    "        X=L[:]\n",
    "        for i in range(len(boxes)):\n",
    "            r=sum(L)\n",
    "            result.append(r)\n",
    "            for j,k in enumerate(X):\n",
    "                if k>i:\n",
    "                    L[j]-=1\n",
    "                if k<=i:\n",
    "                    L[j]+=1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 模拟\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            s = sum(abs(j - i) for j, c in enumerate(boxes) if c == '1')\n",
    "            res.append(s)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        left,right,o = int(boxes[0]),0,0\n",
    "        for i in range(1,len(boxes)):\n",
    "            if boxes[i] == '1':\n",
    "                right += 1\n",
    "                o += i\n",
    "        ans = [o]\n",
    "        for i in range(1,len(boxes)):\n",
    "            o += left - right\n",
    "            if boxes[i] == '1':\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            ans.append(o)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(boxes)):\n",
    "            count = 0\n",
    "            for j in range(len(boxes)):\n",
    "                if i != j and int(boxes[j]) == 1:\n",
    "                    count += abs(j-i)\n",
    "            res.append(count)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        left, right, op = int(boxes[0]), 0, 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "          if boxes[i] == '1':\n",
    "              right += 1\n",
    "              op += i\n",
    "        \n",
    "        ans = [op]\n",
    "        for i in range(1, n):\n",
    "            op = op + left - right\n",
    "            ans.append(op)\n",
    "\n",
    "            if boxes[i] == '1':\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        N = len(boxes)\n",
    "        res = [0]*N\n",
    "\n",
    "        pre = 0\n",
    "        total = 0\n",
    "        for i in range(1,N):\n",
    "            if boxes[i-1]=='1': total+=1\n",
    "            res[i] = pre+total\n",
    "            pre+=total\n",
    "        \n",
    "\n",
    "        pre = 0\n",
    "        total = 0\n",
    "        for i in range(N-2, -1, -1):\n",
    "            if boxes[i+1]=='1': total+=1\n",
    "            res[i] += pre+total\n",
    "            pre+=total\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        pre_dis = [0] * n\n",
    "        suf_dis = [0] * n\n",
    "        cnt = 0\n",
    "        dis_sum = 0\n",
    "        for i in range(n):\n",
    "            dis_sum += cnt\n",
    "            pre_dis[i] = dis_sum\n",
    "            if boxes[i] == '1':\n",
    "                cnt += 1\n",
    "        cnt = 0\n",
    "        dis_sum = 0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            dis_sum += cnt\n",
    "            suf_dis[i] = dis_sum\n",
    "            if boxes[i] == '1':\n",
    "                cnt += 1\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            ans[i] = pre_dis[i] + suf_dis[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        result=[]\n",
    "        for i in range(len(boxes)):\n",
    "            sum1=0\n",
    "            for j in range(len(boxes)):\n",
    "                sum1+=abs(j-i)*int(boxes[j])\n",
    "            result.append(sum1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        '''\n",
    "        dp的思想\n",
    "        1. 目标值分成左右部分\n",
    "        2. answer[i+1]的左右部分，可以根据answer[i]左右部分及boxes当前值计算出来\n",
    "        '''\n",
    "        answer = [0 for i in range(len(boxes))]\n",
    "        left = 0\n",
    "        left_1 = 0\n",
    "        right = 0\n",
    "        right_1 = 0\n",
    "        for i,v in enumerate(boxes):\n",
    "            if boxes[i] == '1' and i > 0:\n",
    "                right += i\n",
    "                right_1 += 1\n",
    "        answer[0] = left + right\n",
    "        for i in range(1, len(boxes)):\n",
    "            if boxes[i-1] == '1':\n",
    "                left_1 += 1\n",
    "            left += left_1\n",
    "            \n",
    "            right -= right_1\n",
    "            if boxes[i] == '1':\n",
    "                right_1 -= 1\n",
    "            answer[i] = left + right\n",
    "        return answer\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        pos = [i for i, c in enumerate(boxes) if c == '1']\n",
    "        answer = list()\n",
    "        for i in range(len(boxes)):\n",
    "            answer.append(sum([abs(p - i) for p in pos]))\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                left[i] = left[i - 1] + cur\n",
    "            cur = cur + (boxes[i] == '1')\n",
    "        cur = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i < n - 1:\n",
    "                right[i] = right[i + 1] + cur\n",
    "            cur = cur + (boxes[i] == '1')\n",
    "        \n",
    "        return [left[i] + right[i] for i in range(n)] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        count = []\n",
    "        for i in range(len(boxes)):\n",
    "            counter=0\n",
    "            for j in range(len(boxes)):\n",
    "                \n",
    "                if j != i:\n",
    "\n",
    "                    if int(boxes[j]) == 1:\n",
    "                        diff=abs(j-i)\n",
    "\n",
    "                        counter=counter + diff\n",
    "            count.append(counter)\n",
    "                \n",
    "        return count\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        n = len(boxes)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        cnt = 0\n",
    "        for i in range(1, n):\n",
    "            if boxes[i - 1] == '1':\n",
    "                cnt += 1\n",
    "            left[i] = left[i - 1] + cnt\n",
    "        cnt = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if boxes[i + 1] == '1':\n",
    "                cnt += 1\n",
    "            right[i] = right[i + 1] + cnt\n",
    "        return [a + b for a, b in zip(left, right)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        return [sum([abs(i - j) for j in range(len(boxes)) if boxes[j] == '1']) for i in range(len(boxes))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, boxes: str) -> List[int]:\n",
    "        \n",
    "        list_baxs = list(boxes)\n",
    "        index_list = [index for index, value in enumerate(boxes) if value == '1']\n",
    "\n",
    "        answer = [0]*len(boxes)\n",
    "        for item in index_list:\n",
    "            for i in range(0, len(boxes)):\n",
    "                if i == item:\n",
    "                    continue\n",
    "                answer[i] += abs(i - item)\n",
    "\n",
    "        return answer"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
